1.二分图
二分图对偶定理:
二分图最大权匹配 二分图最小点权覆盖 二分图最大点权独立集
1.最小点权覆盖
若一个点集 , 使得: , ,那么 便是原图的一个点覆盖。
对于所有满足条件的 , 的最小值即为最小点权覆盖。
-
将二分图的两部分分别与源点/汇点连容量为点权的边
-
二分图内部的边容量设为
最后图的最小割即为原二分图的最小点权覆盖。
考虑这样做的正确性:
二分图的点覆盖中每条边都至少被一个点覆盖,所以没有源点到汇点的路径,是新图的割。
新图的割的边集只可能包含源点与汇点为顶点的边(内部的边容量为 ),那么割掉一条边对应选出这个点。
2.最大点权独立集
若一个点集 , 使得: , , 那么 便是原图的一个点独立集。
对于所有满足条件的 , 的最大值即为最大点权独立集。
由对偶定理和 1. 易得解法,不再赘述。
2020.12.30、2020.12.31 题目
2.最大权闭合子图
对于原图 的一个子图 ,
若: ,有 ,那么 为原图的闭合子图。
对于所有满足条件的 , 的最大值即为原图的最大权闭合子图。
-
对于原图中点权为正的点 ,连接 , 容量为
。 -
对于原图中点权为负的点 ,连接 ,容量为 。
-
对于原图中的边,连接 , 容量为 。
答案即为所有正权点的权值之和减去新图的最小割。
咕咕咕...
2020.12.26 题目
3.最大密度子图
对于原图 的一个子图 ,
该子图的密度为: 。
对于所有子图 ,密度最大的子图即为原图的最大密度子图。
4.对偶图
5.混合图欧拉回路
6.集合划分问题
将元素划分为两个集合 , 满足 且 。
第 件物品被选入 集合花费 的收益,选入 集合花费 的收益。
若 不在同一集合会有 的收益。
若集合 中所有元素在同一集合有 的收益。
求划分的最大收益。(收益可能为负数,可以理解为代价)
-
从源点/汇点向每个点连容量为 的边。
-
之间连容量为 的边。
-
新建一个限制点 ,
-
属于 集合则源点向 连容量为 的边, 向 内所有点连容量为 的边。
-
属于 集合则 向汇点连容量为 的边, 内所有点向 连容量为 的边。
所有的正收益 - 图的最小割 即为最大收益。
点直接连向源汇点的边最多会且只会被割一条。若 被割则表示选入 集合,反之若 被割则表示选入 集合。
被割则表示不要 的收益。
要么被割源汇点的边,表示不要 的收益,要么它连向的所有点到源汇的边被割,满足要求。
可以看出,图的割便是一个选择方案,选择方案也对应一个割。求出最小割即可。
2020.12.28 题目
7.方格问题
类型一:格子之间有要求
格点之间的要求视作边,若是二分图则是最大点权独立集。
类型二:每行、每列、每个格子有要求
对于每行、每列分别建一个点
行与列之间的边对应格子限制,源点与行的边 / 汇点与列的边 对应 行 / 列 的限制。
值得注意的是,这个图也是一个二分图。
8.时间限制
类型一:分层图
对于每一个时刻建立一层图,耗费的时间可以根据不同层数的图连边来刻画。
这样建立的图往往很大,效率低下,尽量不要使用。
[CTSC1999]家园 / 星际转移问题 P4400 [JSOI2008]Blue Mary的旅行
类型二:最小链覆盖
将两件事情可以连续完成刻画为一条边,图的最小链覆盖可以解决一些安排问题。
连续完成的要求一般与时间有关。
P4452 [国家集训队]航班安排 P5769 [JSOI2016]飞机调度
做题记录
2020.12.18 拆点、最大流
P3153 [CQOI2009]跳舞
二分答案 + 拆点 + 最大流
P3163 [CQOI2014]危桥
最大流
2020.12.19 最大流/最小割
*SP839 Optimal Marks
按位考虑 + 最小割
2020.12.21 上下界网络流
P4311 士兵占领
P4843 清理雪道
UVA1440 Inspection
2020.12.22 上下界网络流
P4194 矩阵
2020.12.23 拆点、最大流
UVA12125 March of the Penguins
拆点
*SP4063 Sell Pigs
最大流建模
2020.12.24 最大流/最小割
*P1344 [USACO4.4]Pollutant Control
特殊处理:
在最小割最小的前提下,让割的边最少。
对每一条 的边变为 。
最后 为最小割, 为最少边。
*P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查
最小割建模
2020.12.25 最大流/最小割
UVA1660 Cable TV Network & SP300 Cable TV Network
最小割建模
*P4662 [BalticOI 2008]黑手党
最小割建模
P3191 [HNOI2007]紧急疏散
最大流建模
P2402 奶牛隐藏
最大流建模
2020.12.26 最大权闭合子图
CF1082G Petya and Graph
P4174 [NOI2006]最大获利
P3410 拍照
*P4177 [CEOI2008]order
注意经典模型的转换。
P3749 [六省联考2017]寿司餐厅
*CF103E Buying Sets
特殊条件的运用。
P5295 [北京省选集训2019]图的难题
结论题 + 退流
退流似乎用处不大,毕竟建图的时间肯定小于网络流的时间。
*2020.12.28 集合划分问题
P1361 小M的作物
P1935 [国家集训队]圈地计划
P4313 文理分科 & P1646 [国家集训队]happiness
P4210 土地划分
2020.12.28 最小割
P2598 [ZJOI2009]狼和羊的故事
最小割建模
P6094 [JSOI2015]圈地
上一题的加强版
2020.12.29 最小割
*P3227 [HNOI2013]切糕
最小割建模
P3973 [TJOI2015]线性代数
最小割建模
P5934 [清华集训2012]最小生成树
最小割建模
P1791 [国家集训队]人员雇佣
2020.12.30 二分图
*P5771 [JSOI2016]反质数序列
最大权独立集
P2172 [国家集训队]部落战争
最小路径覆盖
P4589 [TJOI2018]智力竞赛
最小路径覆盖
SP741 STEAD - Steady Cow Assignment
二分图匹配
UVA1194 Machine Schedule
最小点权覆盖
2020.12.31 二分图
P6062 [USACO05JAN]Muddy Fields G
最小点覆盖
P2825 [HEOI2016/TJOI2016]游戏
最大匹配
2021.1.4 费用流
P4068 [SDOI2016]数字配对
2020.1.5 费用流
P4209 学习小组
P4400 [JSOI2008]Blue Mary的旅行
2021.1.6 费用流
P2045 方格取数加强版
P2053 [SCOI2007]修车
*P2050 [NOI2012] 美食节
动态加点费用流
2021.1.8 费用流
P2153 [SDOI2009]晨跑
P2517 [HAOI2010]订货
*P4452 [国家集训队]航班安排
todo list
最大闭合子图,最大密度子图,平面图,混合图欧拉回路,集合划分总结
*P4055 [JSOI2009]游戏
匹配 + 博弈论